package singly_linked_list

import (
    "fmt"

    myErr "data_structure/error"
)

type node[T any] struct {
    data T
    next *node[T]
}

type singlyLinkedList[T any] struct {
    head   *node[T]
    length uint
}

func New[T any]() *singlyLinkedList[T] {
    return &singlyLinkedList[T]{
        head: new(node[T]),
    }
}

func (sl *singlyLinkedList[T]) GetByIndex(index uint) (*node[T], error) {
    if index > sl.length {
        return nil, myErr.ErrorIndexOutOfRange
    }
    node := sl.head
    for i := 0; i < int(index); i++ {
        node = node.next
    }
    return node, nil
}

func (sl *singlyLinkedList[T]) Insert(index uint, data T) error {
    if index > sl.length+1 || index == 0 {
        return myErr.ErrorIndexOutOfRange
    }
    preNode, err := sl.GetByIndex(index - 1)
    if err != nil {
        return err
    }

    var nextNode *node[T]
    if index < sl.length {
        nextNode = preNode.next
    }
    newNode := &node[T]{
        data: data,
        next: nextNode,
    }
    preNode.next = newNode
    sl.length++
    return nil
}

// Reverse 反转链表。
//
// 该函数不需要参数，也不返回任何值。
// 它通过反转链表中的节点连接来反转链表。
func (sl *singlyLinkedList[T]) Reverse() {
    // 如果链表为空或只有一个节点，则无需反转，直接返回。
    if sl.head == nil || sl.head.next == nil {
        return
    }
    var (
        prev, next *node[T]       // 用于指向当前节点的前一个和下一个节点。
        current    = sl.head.next // 从链表的第二个节点开始遍历。
    )

    // 遍历链表，直到当前节点为空。
    for current != nil {
        // 暂存当前节点的下一个节点，以便后续遍历。
        next = current.next
        // 将当前节点的next指针指向前置节点，实现反转。
        current.next = prev
        // 移动prev和current指针，继续处理下一个节点。
        prev = current
        current = next
    }

    // 更新链表头指针，指向新的开始节点。
    sl.head = new(node[T])
    sl.head.next = prev
}

func (sl *singlyLinkedList[T]) Remove(index uint) error {
    pre, err := sl.GetByIndex(index - 1)
    if err != nil {
        return err
    }
    current := pre.next
    next := current.next
    pre.next = next
    current.next = nil
    sl.length--
    return nil
}

func (sl *singlyLinkedList[T]) String() string {
    node := sl.head
    str := "<head>"
    for node.next != nil {
        node = node.next
        str += "->" + fmt.Sprintf("%v", node.data)

    }
    str += "-><nil>"
    return str
}
